package com.zhhe.tree;

import org.omg.CORBA.TRANSACTION_MODE;

import java.util.concurrent.BlockingDeque;

/*
 *Author:ZouHeng
 *Des:
 *Date:2021-01-28  14:13
 */
public class RBTree<T extends Comparable<T>> {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private Node<T> root;
    private int size;

    /**
     * 对红黑树的节点(x)进行左旋转
     *
     * 左旋示意图(对节点x进行左旋)：
     *      px                              px
     *     /                               /
     *    x                               y
     *   /  \      --(左旋)-.           / \                #
     *  lx   y                          x  ry
     *     /   \                       /  \
     *    ly   ry                     lx  ly
     *
     * @param node x
     */
    private void leftRotate(Node<T> node) {
        Node<T> rcNode = node.right;
        node.right = rcNode.left;
        if (rcNode.left != null) {
            rcNode.left.parent = node;
        }

        rcNode.parent = node.parent;
        if (node.parent == null) {
            this.root = rcNode;
        } else {
            if (node.parent.left == node) {
                node.parent.left = rcNode;
            } else {
                node.parent.right = rcNode;
            }
        }
        rcNode.left = node;
        node.parent = rcNode;
    }

    /**
     * 对红黑树的节点(y)进行右旋转
     *
     * 右旋示意图(对节点y进行左旋)：
     *            py                               py
     *           /                                /
     *          y                                x
     *         /  \      --(右旋)-.             /  \                     #
     *        x   ry                         lx    y
     *       / \                                  / \                   #
     *      lx  rx                              rx  ry
     *
     * @param node y
     */
    private void rightRotate(Node<T> node) {
        Node<T> lcNode = node.left;

        node.left = lcNode.right;
        if (lcNode.right != null) {
            lcNode.right.parent = node;
        }
        lcNode.parent = node.parent;
        if (node.parent == null) {
            this.root = lcNode;
        } else {
            if (node.parent.left == node) {
                node.parent.left = lcNode;
            } else {
                node.parent.right = lcNode;
            }
        }
        lcNode.right = node;
        node.parent = lcNode;
    }

    public void insert(T value) {
        Node<T> node = new Node<>(null, null, null, value, RED);
        if (node != null) {
            insert(node);
        }
    }

    private void insert(Node<T> node) {
        //将红黑树当作二叉查找树插入
        Node<T> temp = this.root;
        Node<T> item = null;
        while (temp != null) {
            item = temp;
            int cmp = node.value.compareTo(temp.value);
            if (cmp < 0) {
                temp = temp.left;
            } else {
                temp = temp.right;
            }
        }
        node.parent = item;
        if (item != null) {
            int cmp = node.value.compareTo(item.value);
            if (cmp < 0) {
                item.left = node;
            } else {
                item.right = node;
            }
        } else {
            this.root = node;
        }

        node.color = RED;

        //将它重新修正为一颗二叉查找树
        insertFixUp(node);
    }

    private void insertFixUp(Node<T> node) {
        Node<T> parent, gParent;

        //如果父结点存在，并且父结点的颜色是红色
        while ((parent = node.parent) != null && isRed(parent)) {
            gParent = parent.parent;

            //父结点是祖父结点的左孩子
            if (parent == gParent.left) {
                // Case 1条件：叔叔节点是红色
                Node<T> uncle = gParent.right;
                if (uncle != null && isRed(uncle)) {
                    uncle.color = BLACK;
                    parent.color = BLACK;
                    gParent.color = RED;
                    node = gParent;
                    continue;
                }
                // Case 2条件：叔叔是黑色，且当前节点是右孩子
                if (node == parent.right) {
                    leftRotate(parent);
                    //node和parent交换
                    Node<T> tmp = parent;
                    parent = node;
                    node = tmp;
                }
                // Case 3条件：叔叔是黑色，且当前节点是左孩子。
                parent.color = BLACK;
                gParent.color = RED;
                rightRotate(gParent);
            } else {
                //若“z的父节点”是“z的祖父节点的右孩子”
                // Case 1条件：叔叔节点是红色
                Node<T> uncle = gParent.left;
                if ((uncle!=null) && isRed(uncle)) {
                    setBlack(uncle);
                    setBlack(parent);
                    setRed(gParent);
                    node = gParent;
                    continue;
                }

                // Case 2条件：叔叔是黑色，且当前节点是左孩子
                if (parent.left == node) {
                    Node<T> tmp;
                    rightRotate(parent);
                    tmp = parent;
                    parent = node;
                    node = tmp;
                }

                // Case 3条件：叔叔是黑色，且当前节点是右孩子。
                setBlack(parent);
                setRed(gParent);
                leftRotate(gParent);
            }
        }
        // 将根节点设为黑色
        setBlack(this.root   );
    }

    public void remove(T value) {
        if (get(value) != null) {
            remove(get(value));
        }
    }

    private void remove(Node<T> node) {
        // 被删除节点的"左右孩子都不为空"的情况。
        if (node.left != null && node.right != null) {
            Node<T> minNode = node.right;
            while (minNode.left != null) {
                minNode = minNode.left;
            }
            // "node节点"不是根节点(只有根节点不存在父节点)
            if (node.parent != null) {
                if (node.parent.left == node) {
                    node.parent.left = minNode;
                } else {
                    node.parent.right = minNode;
                }
            } else {
                this.root = minNode;
            }
        }
    }

    private boolean isRed(Node<T> node) {
        return node.color == true;
    }

    private void setBlack(Node<T> node) {
        node.color = BLACK;
    }

    private void setRed(Node<T> node) {
        node.color = RED;
    }

    public Node<T> get(T value) {
        return get(root, value);
    }

    private Node<T> get(Node<T> node, T value) {
        if (node == null) {
            return null;
        }
        int cmp = value.compareTo(node.value);
        if (cmp < 0) {
            return get(node.left, value);
        } else if (cmp > 0) {
            return get(node.right, value);
        }else {
            return node;
        }
    }


    private class Node<T> {
        private Node<T> right;
        private Node<T> left;
        private Node<T> parent;
        private T value;

        /**
         * 结点颜色
         * 红色为true，黑色为false
         */
        private boolean color;

        public Node(Node<T> right, Node<T> left, Node<T> parent, T value, boolean color) {
            this.right = right;
            this.left = left;
            this.parent = parent;
            this.value = value;
            this.color = color;
        }
    }
}
